import java.util.ArrayList;

/**
 * @version Create on 2012-11-13
 * @author Yinzi Chen
 */

public class UniqueBinarySearchTreesII {
	class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
			left = null;
			right = null;
		}
	}

	public ArrayList<TreeNode> build(int from, int to) {
		ArrayList<TreeNode> res = new ArrayList<TreeNode>();
		if (from > to) {
			res.add(null);
			return res;
		}
		for (int i = from; i <= to; ++i) {
			ArrayList<TreeNode> l = build(from, i - 1);
			ArrayList<TreeNode> r = build(i + 1, to);
			for (int j = 0; j < l.size(); ++j) {
				for (int k = 0; k < r.size(); ++k) {
					TreeNode root = new TreeNode(i);
					root.left = l.get(j);
					root.right = r.get(k);
					res.add(root);
				}
			}
		}
		return res;
	}

	public ArrayList<TreeNode> generateTrees(int n) {
		return build(1, n);
	}

	public static void main(String[] args) {

	}

}
